#include "LinkTree.h"

// TreeNode
TreeNode::TreeNode(const ElementType &element) : data(element)
{
    parents = child = nextSbling = nullptr; // 初始化
}

void TreeNode::Contact(TreeNode *parents)
{
    if (!parents)
        return;

    this->parents = parents;
    // 头插
    this->nextSbling = parents->child;
    parents->child = this;
}

void TreeNode::Didcontact(TreeNode *parents)
{
    if (parents == nullptr || this->parents != parents)
        return;

    TreeNode *travelpoint = parents->child; // 从父母的第一个孩子开始遍历寻找
    if (this == parents->child)
    {
        parents->child = this->nextSbling;
    }
    else
    {
        while (travelpoint->nextSbling != nullptr)
        {
            if (travelpoint->nextSbling == this)
            {
                travelpoint->nextSbling = this->nextSbling;
                break;
            }
            travelpoint = travelpoint->nextSbling;
        }
    }
    this->parents = this->nextSbling = nullptr;
}

void TreeNode::show(TreeNode *node, int depth)
{
    // 递归终止条件
    if (node == nullptr)
        return;
    for (int i = 0; i < depth; i++)
        std::cout << " ";
    // 排除根节点打印
    if (node->parents != nullptr)
    {
        if (depth > 0)
            std::cout << "|_";
        std::cout << node->data << std::endl;
    }
    // 深度优先遍历，递归
    show(node->child, depth + 1);
    show(node->nextSbling, depth);
}

void TreeNode::FreeNode(TreeNode *node)
{
    // 终止条件
    if (node == nullptr)
        return;
    FreeNode(node->child);
    FreeNode(node->nextSbling);
    delete node;
}

TreeNode *TreeNode::FindNode(TreeNode *node, const ElementType &element)
{
    if (node == nullptr)
        return nullptr;

    if (node->data == element && node->parents != nullptr)
        return node;

    TreeNode *target = FindNode(node->child, element);
    if (target)
        return target;

    target = FindNode(node->nextSbling, element);
    if (target)
        return target;

    return nullptr;
}

void TreeNode::FindNode(TreeNode *node, const ElementType &element, DynamicArray &a)
{
    if (node == nullptr)
        return;

    if (node->data == element && node->parents != nullptr)
        a.InsertTail(node);

    FindNode(node->child, element, a);

    FindNode(node->nextSbling, element, a);
}

int TreeNode::GetNodeHeight(TreeNode *node)
{
    if (node == nullptr)
        return 0;

    int Height = 0;
    // 找最高的子树
    TreeNode *travelPoint = node->child;
    while (travelPoint != nullptr)
    {
        int height = GetNodeHeight(travelPoint);
        Height = Height > height ? Height : height;
        travelPoint = travelPoint->nextSbling;
    }
    // 自身高度= 最高子树高度+1
    return Height + 1;
}

TreeNode *TreeNode::Getparents()
{
    return parents;
}

std::string &TreeNode::GetData()
{
    return data;
}

void TreeNode::SetData(const ElementType& element)
{
    data= element;
}

// LinkTree

LinkTree::LinkTree()
{
    root = new TreeNode("");
}

LinkTree::LinkTree(const ElementType &element)
{
    root = new TreeNode(element);
}

TreeNode *LinkTree::GetRoot()
{
    return root;
}

void LinkTree::show()
{
    root->show(root, -1);
}

LinkTree::~LinkTree()
{
    TreeNode::FreeNode(root);
}

DynamicArray LinkTree::FindByElement(const ElementType &element)
{
    DynamicArray a;
    TreeNode::FindNode(root, element, a);
    return a;
}

// TreeNode *LinkTree::FindByElement(const ElementType &element)
// {
//     return TreeNode::FindNode(root, element);
// }

int LinkTree::GetTreeHeight()
{
    return TreeNode::GetNodeHeight(root);
}

std::string LinkTree::GetNodepath(TreeNode *node)
{
    if (node == nullptr)
        return std::string();

    std::string path = node->GetData();
    while (node->Getparents() != nullptr)
    {
        path = node->Getparents()->GetData() + "/" + path;
        node = node->Getparents();
    }
    return path;
}
